The independent values with which the color device can be addressed are called colorants or inks. For purposes of generality, the physically achievable values for these colorants range from 0 to 100%. A color reproduction device with n colorants will be called a printer or an n-ink process. A typical device we have in mind is a multidimensional color printer with n colorants such as a cmyk offset printing press, but the invention can also be applied to other devices such as color displays, color photography or slide makers.
With colorants space is meant an n-dimensional space with n the number of independent variables with which the printer can be addressed. In the case of an offset printing press the dimension of the space corresponds to the number of inks of the printer. With color space is meant a space that represents a number of quantities of an object that characterize its color. In most practical situations, colors will be represented in a 3-dimensional space such as the CIE XYZ space. However, also other characteristics can be used such as multispectral values based on filters that are not necessarily based on a linear transformation of the color matching functions to represent color. A typical example is an n-dimensional space of which the axes correspond to densities.
With colorants gamut or colorant domain is meant the delimited space in colorant space of colorant combinations that are physically realizable by a given printer, taking into account possible extra limitations on colorant combinations. In this invention it is supposed that colorant limitations are preferentially specified by mathematical formulas that describe the boundaries of the desired colorant gamut.
The colorant gamut of a cmyk offset press for example is delimited by a linear condition that limits the sum of the four colorant (for example to 340%). A printer model is a mathematical relation that expresses color values in function of colorant for a given printer. The variables for the colorant are denoted as c.sub.1, c.sub.2, . . . c.sub.n with n the dimension of the colorant space. An n-ink process is completely characterized by its colorant gamut with a number of colorant limitations and the printer model. Because of this close relationship between an n-ink process and the printer model, the operations typical for a printer model are also defined for the n-ink process. With inverting an n-ink process is meant that the corresponding printer model is inverted. The transformation of an n-ink process to color space on the other hand is equivalent to the transformation of the corresponding colorant domain to color space by making use of the printer model. If an n-ink process is given with colorant limitations in the colorant domain and if an m-ink process is deduced from this n-ink process by setting n-m colorant to constant values in the printer model of the n-ink process, the colorant limitations are inherited by this m-ink process if the colorant gamut of the m-ink process is restricted by colorant limitations obtained by setting the n-m colorant in the colorant limitations of the colorant gamut of the n-ink process to their constant values.
Extracting an m-ink process out of an n-ink process with m&lt;n, means that n-m out of the n colorant in the printer model are replaced by a constant value. The colorant of such an m-ink process vary between the minimum and maximum values they can have according to the colorant gamut of the n-ink process and the colorant limitations are inherited by the m-ink process. The m-ink process is called the extracted m-ink process of the n-ink process.
If an m-ink process is extracted from an n-ink process, and the n-m out of the n colorant in the printer model of the n-ink process are replaced by their minimum or maximum value as defined by the colorant gamut of the n-ink process, the m-ink process is called an m-ink boundary process of the n-ink process. In general there are ##EQU1## m-ink boundary processes of an n-ink process. The colorant in the colorant gamut of an m-ink boundary process vary between the minimum and maximum values they can have according to the colorant gamut of the n-ink process and the colorant limitations are inherited by the m-ink process. With color gamut is meant a delimited region in color space, containing colors that are physically realizable by a given printer, taking into account possible extra limitations on colorant combinations.
A color gamut is completely determined by its boundaries. In a 3-dimensional color space these boundaries are surfaces, and hence there will be surfaces in colorant space that map to the color gamut boundaries. In general several kinds of colorant surfaces should be taken into account, but for well-behaved printers the color gamut is, by definition, exactly determined by the transformation of the colorant domains of the 2-ink boundary processes of the n-ink process to color space. It can be shown that this condition is equivalent with saying that in a n-ink process, a colorant combination lies inside the color gamut if there are at least three colorant that can be changed both positively as negatively. Such surfaces in colorant space are called physical colorant boundaries that are transformed by the printer model to the physical color boundaries in color space. The envelope of the physical color boundaries determines the boundaries of the physical color gamut of the n-ink process. In the case of an s-dimensional color space, the dimension of the boundaries is s-1. Physical colorant boundaries correspond in this case to the domains of the (s-1)-ink boundary processes of the n-ink process. The physical color boundaries are obtained by transforming the domains of the (s-1)-ink boundary processes of the n-ink process to color space.
The color gamut of a printer is certainly one of its most important characteristics. An explicit representation of this gamut is highly desirable, for example, to enable the optimal reproduction of images that contain colors that fall outside the color gamut of the printer.
Because our invention is based on the use of a printer model, a few more words of explanation are given on the subject of printer models.
The Neugebauer Equations
Different mathematical expressions have been proposed to model printing processes, along which the Neugebauer equations are certainly the most known ones.
The Neugebauer equations reflect how color originates in halftone printing. The printing with three inks c.sub.1, c.sub.2 and c.sub.3 by means of three halftone screens results theoretically in eight possible combinations of colorant overlap, called the Neugebauer primaries. If the size of the halftone dots is small enough not to be resolvable by the eye, the resulting color is a weighted sum of the tristimulus values of these primaries. For a 3-ink process, the Neugebauer equation for the X tristimulus value is given by EQU X.sub.(c1,c2,c3) =a.sub.W X.sub.W +a.sub.1 X.sub.1 +a.sub.2 X.sub.2 +a.sub.3 X.sub.3 +a.sub.12 X.sub.12 +a.sub.13 X.sub.13 +a.sub.23 X.sub.23 +a.sub.123 X.sub.123
If it is assumed that the relative positions of the halftone dots are random, the Neugebauer equations can be calculated from the Demichel equations that predict the fraction of each combination of the three inks as a function of their respective dot percentages c.sub.1, c.sub.2 and c.sub.3, and this leads to the Neugebauer equations in their most often encountered form: EQU a.sub.W =(1-c.sub.1)(1-c.sub.2)(1-c.sub.3) EQU a.sub.1 =(c.sub.1)(1-c.sub.2)(1-c.sub.3) EQU a.sub.2 =(1-c.sub.1)(c.sub.2)(1-c.sub.3) EQU a.sub.3 =(1-c.sub.1)(1-c.sub.2)(c.sub.3) EQU a.sub.23 =(1-c.sub.1)(c.sub.2)(c.sub.3) EQU a.sub.13 =(c.sub.1)(1-c.sub.2)(c.sub.3) EQU a.sub.12 =(c.sub.1)(c.sub.2)(1-c.sub.3) EQU a.sub.123 =(c.sub.1)(c.sub.2)(c.sub.3)
in which c.sub.1, c.sub.2 and c.sub.3 represent the dot percentages of the three inks. The equations for the Y and Z values are obtained by replacing the X values by the corresponding Y and Z values respectively. The extension of the Neugebauer equations for n inks is straightforward.
According to one interpretation, the Neugebauer equations predict the X, Y and Z tristimulus values by means of trilinear interpolation from the corresponding tristimulus values of the 8 Neugebauer "primaries". If the Neugebauer equations are used as multilinear interpolation formulae, they can be used to model any color device in any color space.
Working out the Demichel coefficients in the Neugebauer equations and rearranging the terms results in the following set of polynomial expressions: EQU X=k.sub.0 +k.sub.1 c.sub.1 +k.sub.2 c.sub.2 +k.sub.3 c.sub.3 +k.sub.12 c.sub.1 c.sub.2 +k.sub.13 c.sub.1 c.sub.3 +k.sub.23 c.sub.2 c.sub.3 +k.sub.123 c.sub.2 c .sub.3 EQU Y=1.sub.0 +1.sub.1 c.sub.1 +1.sub.2 c.sub.2 +1.sub.3 c.sub.3 +1.sub.12 c.sub.1 c.sub.2 +1.sub.13 c.sub.1 c.sub.3 +1.sub.23 c.sub.2 c.sub.3 +1.sub.123 c.sub.1 c.sub.2 c.sub.3 EQU Z=m.sub.0 +m.sub.1 c.sub.1 +m.sub.2 c.sub.2 +m.sub.3 c.sub.3 +m.sub.12 c.sub.1 c.sub.2 +m.sub.13 c.sub.1 c.sub.3 +m.sub.23 c.sub.2 c.sub.3 +m.sub.123 c.sub.1 c.sub.2 c.sub.3
This leads to an interpretation of the Neugebauer equations as a set of "interpolating polynomials". The coefficients can be calculated from the X, Y and Z values of the eight Neugebauer primaries, or they can be obtained by means of a regression technique on a large set of color-colorant combinations. The Neugebauer equations can be graphically represented. For a given color XYZ, each one of the three Neugebauer equations represents a curved surface in the colorant space. The situation is depicted for a common cmy printing process in FIG. 1.
Improving the Precision of the Neugebauer Printing Model.
Real printing processes seldom behave exactly according to the physical model on which the Neugebauer equations are based. Various modifications of the Neugebauer equations have therefore been suggested to improve their precision, among which the n-modified and the spectral Neugebauer equations are only cited. The interpretation of the Neugebauer equations as interpolating polynomials leads to the introduction of additional higher order terms, while their interpretation as trilinear interpolation suggests the concept of "piece-wise trilinear interpolation" to improve the accuracy of the model. The latter method is also known under the name of cellular or localized Neugebauer equations ("LNE"). The different subdomains are called the Neugebauer cells. More information on these models is found in the article by Rollestone Robert and Balasubramanian Raja (1993), "Accuracy of Various Types of Neugebauer Model", 1993 IS&T and SID's Color Imaging Conference: Transforms & Transportability of Color, pp. 3-37.
Calculation of the Color Gamut Boundaries.
An example of a first heuristic method is described in "Derivation of 3-dimensional gamut descriptions for graphic arts output devices", presented at TAGA 94 by William Kress and Michael Stevens.
According to this method, the colorant gamut is sampled and the resulting colorant combinations are evaluated by means of a printer model. The resulting colors are then classified in "bins" of, for example, different CITE lightness values. The envelope of the colors that lie within one such a "bin" reflects an approximation of the shape of the color gamut at the corresponding constant lightness value. The method is conceptually simple, but has a number of drawbacks. In the first place a large set of samples in the colorant gamut is needed to achieve a reasonable description of the color gamut boundaries. Hence this method is quite slow and the processing time for this method increases exponentially with the number of colorant. A second problem is that from a mathematically point of view it is difficult to determine exactly the boundaries of the color gamut per lightness level from a set of discrete points. Particularly the detection of holes or several contours per lightness level is rather complicated, if not impossible. Moreover, the method is not always robust because it may fail to detect the exact contours if the sampling distance in the colorant space is too large so that neighboring points ih colorant space are transformed to colors in color space that are not seen as connected by the color gamut boundary detection method.
According to a second approach, the gamut boundaries are "explored" in one of the color spaces using heuristic techniques. A "start color" is first selected that is known to fall inside the reproducible color gamut. This color is then incrementally changed keeping two of the three dimensions (for example hue and lightness) constant. The changed color is then separated and the colorant values are evaluated. If they fall within the colorant gamut, the corresponding color is assumed to fall within the printable color gamut and a next increment is added to the color. If, however, the set of colorant values falls outside the colorant gamut, a point of the colorant gamut boundary is assumed to lie in between the current and the previous separated color. By returning to the last color that still was within the color gamut and making the color increment smaller, the exact position of the point of the color gamut boundary can be determined with any desired precision. By selecting a sufficient number of "start colors" and a sufficient number of directions for the color change, the boundaries of the color gamut can be reasonably estimated. This method, however, also has a number of drawbacks. The method mainly works in color space, so the printer model has to be inverted.
Till now this is almost always done by iterative methods. If several colorant combinations give rise to the same color, only one solution will be found. If that solution lies outside the colorant gamut, wrong conclusions will be drawn for the color gamut if at least one of the other solutions would be inside the colorant domain. A second problem is that it can fail when the color gamut is concave or when per cross section several contours have to be determined. A third drawback is that the heuristic nature of the procedure leads to very long calculations since many more points need to be evaluated than are obtained for the description of the gamut boundary itself. A faster version of this method is represented in the article "The color gamut obtainable by the combination of subtractive color dyes", Journal of Imaging science, Vol. 30, No. 1, 1986 by N. Otha. Per lightness plane a border point is searched for and the next border point is detected by looking radially around this point. From this new border point the next border point is detected again by radially looking around it. This last procedure is repeated until the first border point is reached again. In this way concave contours can be detected, but nevertheless this iterative method is still quite slow, the printer model has to be inverted and multiple contours are not detected.
A third approach is described in the article by Masao Inui, "Fast Algorithm for Computing Color Gamuts", Color Research and Application, Vol. 18, No. 5, October 1993. In order to calculate a gamut descriptor of a 3-ink process, the following procedure is performed:
Step 1: The lightness values at the eight vertices of the dye delimited solid are calculated for zero and maximum amounts; PA1 Step 2: For a given lightness, the locations of several equilightness points on the edges of the dye delimited solid are computed; PA1 Step 3: Loci connecting these points on the faces of the dye delimited solid are computed; PA1 Step 4: The loci are mapped into color space to produce the boundary of the color gamut.
According to the article, the loci of the equilightness points on the edges of the dye solid are computed as follows. Since at the edge of the color solid one of the colorant is equal to its minimum or maximum value, there are effectively only two colorant available as variables to achieve the desired lightness value. One of these variables can be used as a parameter, leaving only one value left to iterate on. One dimensional Newton-Raphson is used to determine the value of this remaining variable that results in the desired lightness value.
The above method is claimed to work very fast, but its weak point is that it relies on Newton Raphson iteration. Depending on the printer model, there may be several possible solutions, but only one solution will be found with iterative methods. Nevertheless, if several start points would be used to find all the solutions, it is not possible to know which colorant combination belongs to (which one of) the previous solution(s), i.e. no information is available about the connectivity between the different solutions.
Moreover, for unconventional processes some boundaries of the color gamut are not obtained by mapping the edges of the colorant cube to color space. An example of such a 3-ink process was found in printing yellow (y), cyan (c) and green (g) inks. The XYZ and corresponding CIELAB values of the Neugebauer primaries of this process are given in Table 1. The first column corresponds to the 8 possible combinations of ink overlap. An evaluation reveals that for this process approximately half of the realizable colorant combinations yields colors that lie outside the color gamut as it is defined by the mapping of the edges of the colorant cube to color space. FIG. 2 shows a cross section of the color gamut in CIELAB at a constant L* value. The solid lines correspond to the intersection with the mapping of the edges of the colorant cube to color space. The shaded area represents colors that lie outside the gamut defined by the physical boundaries. The outer curve represents the intersection with the object color solid, also known as the MacAdam limits.
TABLE 1 ______________________________________ XYZ and CIELAB values of the Neugebauer primaries of a non-conventional 3-ink process. X Y Z L* a* b* ______________________________________ white 100.0 100.0 100.0 100.0 0.0 0.0 y 64.8 66.2 10.5 85.1 -3.1 80.1 g 19.7 29.8 7.0 61.5 -43.1 51.2 c 25.7 33.6 69.2 64.7 -29.7 -37.8 yg 14.1 19.6 1.7 51.4 -30.0 64.6 yc 11.1 19.8 6.9 51.6 -51.0 34.4 gc 4.7 11.2 4.6 39.9 -60.9 24.6 ygc 3.0 6.8 1.1 31.4 -49.3 37.8 ______________________________________
In many situations, it is not possible to print all the colorant combinations. A typical example occurs for the cmyk offset process, for which the sum of the inks is limited to 340%. For some other colorant combinations, there may also be some printing problems if three times 100% is printed on top of each other, although the total amount of colorant may be larger than 300%. To avoid such effects, several colorant limitations may be given in the colorant domain.
To determine the color gamut of a printer with a number of colorant limitations, previous methods should be adapted. Some of them can be easily extended such as the first method, but all the previously cited problems remain. However, for the last method, the iteration becomes more complex so that even in the case of simple mathematical printer models there will be multiple solutions which are difficult to find. Moreover, if all the different solutions could be found, also in this case it is almost impossible to connect the different solutions to form one or several contours.
Finally, also the extension of previous methods to more than three colorant is not always straightforward. Most methods suppose that there is a one to one relation between printers with three colorant and the color values. For printers with more than three colorant this is certainly no longer the case.